/*
 * Запертые двери
 */

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//#define DEBUG 1
#define MEMDEBUG 1

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif

#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))

/* queue */
struct queue {
	char *data;
	size_t _data_size;

	int head;
	int n;
	int _max;
};

/* autoarray */
struct vector {
	char *data;
	size_t _elem_size;

	int n;
	int _max;
};


struct state {
	int8_t x, y;
	uint8_t keys;
	int prev;
	int move;
};

/* {{{ function prototypes */
/* memory allocation wrappers */
void *s_calloc(size_t n, size_t size);
void *s_malloc(size_t size);
void *s_realloc(void *oldptr, size_t newsize);

struct queue *queue__new(const int n, const size_t elem_size);
int queue__push(struct queue *q, const void *p);
int queue__pop(struct queue *q, void *buf);
int queue__cleanup(struct queue *q);

/*
 * int vector_init(struct vector *v, int p);
 * int vector_append(struct vector *v, int a);
 * int vector_sort(struct vector *v, int (*cmpf)(const void *, const void *));
 * int vector_cleanup(struct vector *v);
 */

struct vector *vector__new(size_t elem_size, int p);
int vector__append(struct vector *v, const void *app);
char *vector__get_by_idx(struct vector *v, const int idx);
int vector__cleanup(struct vector *v);

struct dll_node *dll_insert(struct dll_node *node, struct dll_node *ins);
struct dll_node *dll_delete(struct dll_node *node);
void dll_mergesort(struct dll_node *head, int (*cmp)(const void *, const void *));

/* mergesort (with copy array optimization) */
void mergesort(void *base, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *));

struct pqueue *pqueue__new(const size_t elem_size, int exp,
		const bool autoexpand, int (*f)(const void *, const void *));
int pqueue__insert(struct pqueue *pq, const void *elem);
int pqueue__extract(struct pqueue *pq, void *buf);
int pqueue__cleanup(struct pqueue *pq);

void adjl_dll_connect(struct adjlist_dll *, const int, const int);
void adjl_dll_cleanup(struct adjlist_dll *al);

/* misc */
struct dll_node *vector_to_dll_list(struct vector *v);
char *bytes_to_str(const void *ptr, const size_t size);

/* KMP */

/* }}} */

/* {{{ memory allocation wrappers */
extern void *s_calloc(size_t n, size_t size)
{
	void *ptr;
	ptr = calloc(n, size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern void *s_malloc(size_t size)
{
	void *ptr;
	ptr = malloc(size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern void *s_realloc(void *oldptr, size_t newsize)
{
	void *newptr;
	newptr = realloc(oldptr, newsize);
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): realloc oldptr %p for new size %lu (%.3f MiB)\n",
			__func__, oldptr, newsize, (float) newsize / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
	return newptr;
}
/* }}} */

/* {{{ queue */
extern struct queue *
queue__new(const int n, const size_t elem_size)
{
	struct queue *q = NULL;

	assert(n > 1);
	assert(elem_size > 0);

	q = (struct queue *) s_malloc(sizeof *q);
	q->data = (char *) s_calloc(n, elem_size);
	q->_data_size = elem_size;
	q->head = 0;
	q->n = 0;
	q->_max = n;

	return q;
}

extern int
queue__push(struct queue *q, const void *p)
{
	assert(q != NULL);
	assert(p != NULL);

	if (q->n >= q->_max) {
		debug_fprintf((stderr, "%s(): q->n (%d) >= q->_max (%d), can't push any deeper :-(\n",
				__func__, q->n, q->_max));
		return -1; /* can't push any further */
	}

	memcpy(q->data + ((q->head + q->n++) % q->_max) * q->_data_size, p, q->_data_size);
	debug_fprintf((stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n));

	return 0;
}

extern int
queue__pop(struct queue *q, void *buf)
{
	assert(q != NULL);
	assert(buf != NULL);

	memcpy(buf, q->data + (q->head) * q->_data_size, q->_data_size);
	q->head = (q->head + 1) % q->_max;
	q->n--;
	debug_fprintf((stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n));

	return 0;
}

extern int
queue__cleanup(struct queue *q)
{
	S_assert(q != NULL);
	if (q == NULL)
		return -1;

	if (q->_max == 0 || q->data == NULL)
		return 1;

	free(q->data);
	q->data = NULL;
	free(q);

	return 0;
}
/* }}} */

/* {{{ autoarray */
extern struct vector *
vector__new(size_t elem_size, int p)
{
	struct vector *v = NULL;

	if (p < 0)
		p = 0;

	v = (struct vector *) s_malloc(sizeof *v);
	v->_max = 1 << p;
	v->_elem_size = elem_size;
	v->n = 0;
	v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);

	return v;
}

extern int
vector__append(struct vector *v, const void *app)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max == 0) {
		/* weird input, fix it */
		ret |= 2;
		debug_fprintf((stderr, "%s(): v->_max is 0, which means that your "
					"autoarray (v=%p) is messed up. trying to fix this.\n",
					__func__, (void*) v));
		if (v->_elem_size == 0) {
			ret |= 4;
			fprintf(stderr, "%s(): can't fix this mess, bailing out (%d)\n",
					__func__, ret);
			return ret;
		} else {
			v->_max = 1;
			v->n = 0;
			v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);
		}
	}

	if (v->n + 1 >= v->_max) {
		v->data = (char *) s_realloc(v->data, v->_elem_size * (v->_max *= 2));
	}
	memcpy(v->data + (v->n++) * v->_elem_size, app, v->_elem_size);

	return ret;
}

extern char *
vector__get_by_idx(struct vector *v, const int idx)
{
	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (NULL)\n",
				__func__);
		return NULL;
	}

	if (v->_elem_size == 0) {
		fprintf(stderr, "%s(): whoah, looks like your vector is messed up big time (NULL)\n",
				__func__);
		return NULL;
	}

	if (idx < 0 || idx >= v->n) {
		fprintf(stderr, "%s(): index out of range %d (v->n=%d)\n",
				__func__, idx, v->n);
		return NULL;
	}

	return v->data + (idx) * v->_elem_size;
}

extern int
vector__cleanup(struct vector *v)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max > 0) {
		v->_max = v->n = 0;
		free(v->data);
		v->data = NULL;
	} else {
		ret |= 1;
	}

	/* TODO: improve logic */
	debug_fprintf((stderr, "%s(): freeing v=%p\n", __func__, (void*) v));
	free(v);

	return ret;
}
/* }}} */

int
play(char map[50][50], const int n, const int m, struct state spawn)
{
	struct vector *Q;
	static bool visited[50][50][1 << 6];
	register int r = 0;
	int i, j;
	struct state cur, nxt;
	void *ptr;
	static const int d[][2] = { { 1, 0 }, { 0, -1 }, { -1, 0 }, { 0, 1} };

	Q = vector__new(sizeof (struct state), 10);
	vector__append(Q, &spawn);
	cur = spawn;
	visited[cur.x][cur.y][cur.keys] = true;

#define CHK_ARR_BOUNDS(a, b, n, m) \
		(a.x + b[0] < n && a.x + b[0] >= 0 &&\
		 a.y + b[1] < m && a.y + b[1] >= 0)
#define NEED_KEY(s, d, map) \
		(!isupper(map[s.x+d[0]][s.y+d[1]]) ||\
		 (isxdigit(map[s.x + d[0]][s.y + d[1]]) &&\
		 (01 == ((s.keys >> (map[s.x + d[0]][s.y + d[1]] - 'A')) & 01)))) //SUDDENLY, LISP!
	r = i = j = 0;
	while (map[cur.x][cur.y] != '1')
	{
		debug_fprintf((stdout, "x=%2hhd y=%2hhd keys=%02hho move=%d prev=%4d [%5d]\n",
				cur.x, cur.y, cur.keys, cur.move, cur.prev, r));

		nxt = cur;

		for (int k = 0; k < sizeof d / sizeof d[0]; ++k)
		{
			if (CHK_ARR_BOUNDS(cur, d[k], n, m) &&
			    map[cur.x + d[k][0]][cur.y + d[k][1]] != '#' &&
			    !visited[cur.x + d[k][0]][cur.y + d[k][1]][cur.keys] &&
			    NEED_KEY(cur, d[k], map))
			{
				nxt.keys = cur.keys;

				if (map[cur.x+d[k][0]][cur.y+d[k][1]] <= 'f' &&
				    map[cur.x+d[k][0]][cur.y+d[k][1]] >= 'a')
				{
					nxt.keys = cur.keys | 1 <<
							(map[cur.x+d[k][0]][cur.y+d[k][1]] - 'a');
				}

				nxt.x = cur.x + d[k][0];
				nxt.y = cur.y + d[k][1];
				nxt.prev = r;
				nxt.move = cur.move + 1;
				vector__append(Q, &nxt);

				debug_fprintf((stdout, "\tenqueued next tile '%c'\n",
						map[nxt.x][nxt.y]));

				visited[nxt.x][nxt.y][nxt.keys] = true;
			}
		}

		ptr = vector__get_by_idx(Q, ++r);
		if (NULL == ptr)
		{
			fprintf(stderr, "%s():%d: ptr is NULL. wat do?\n", __func__, __LINE__);
			vector__cleanup(Q);
			return -1;
		}
		else
		{
			cur = * (struct state *) ptr;
		}
	}
#undef CHK_ARR_BOUNDS
#undef NEED_KEY

	vector__cleanup(Q);
	return cur.move;
}

int
main(int argc, char **argv)
{
	int n, m;
	int i, j;
	int c;
	static char map[50][50];
	static char line[52];
	struct state spawn;

	(void) fgets(line, sizeof line, stdin);
	sscanf(line, "%d %d", &n, &m);

	i = j = 0;
	while (i < n)
	{
		c = fgetc(stdin);

		S_assert(c != EOF);
		if (isspace(c))
		{
			S_assert(c == '\n');
			j = 0;
			i++;
			continue;
		}

		if (c == '0')
		{
			spawn.x = i;
			spawn.y = j;
			spawn.keys = 00;
			spawn.prev = -1;
			spawn.move = 0;
		}
		map[i][j++] = c;
	}

	printf("%d\n", play(map, n, m, spawn));

	return 0;
}
